#include <stdio.h>

#include "../esyio.h"
#include "../linklist.h"


// 头插法
void ReverseV1(LinkList L) {
    LNode *p = L->next;
    L->next = NULL;
    while (p) {
        LNode *q = p->next;
        p->next = L->next;
        L->next = p;
        p = q;
    }
}

// https://zhuanlan.zhihu.com/p/105749135
/*
 *  初始化两个指针，p 指向链表的第一个节点，q 用来辅助交换节点。
 *  进入循环，遍历链表，直到 p 指向最后一个节点（即 p->next 为空）。
 *  在循环中，将 q 指向 p 的下一个节点，即当前节点的后继节点。
 *  将 p 的 next 指针指向 q 的后继节点，这样 p 节点就脱离了原来的位置，而指向了它原来的下一个节点。
 *  接着，将 q 的 next 指针指向链表的头节点，也就是将当前节点 q 移动到链表的头部。
 *  最后，将链表的头指针指向 q，完成一次节点的交换。
 *  重复上述步骤，直到 p 指向最后一个节点，此时链表已经完成反转。
 *
 */
void ReverseV2(LinkList L) {
    LNode *p = L->next;
    LNode *q;
    while (p->next) {
        q = p->next;
        p->next = q->next;
        q->next = L->next;
        L->next = q;
    }
}



// 反转链表中从第 m 个节点到第 n 个节点的部分
LinkList ReverseFromTo(LNode *L, int m, int n) {
    // pre: 待反转部分的前一个节点
    // p: 待反转部分的第一个节点
    // q: 待反转部分的最后一个节点
    // t: 待反转部分的后一个节点
    LNode *pre = L, *p = L->next, *q = p, *t = p;

    int i = 1; // 初始化计数器

    // 移动指针，找到待反转部分的前一个节点
    while (i < m) {
        pre = p;
        p = p->next;
        ++i;
    }

    // 如果 m < n，则再移动指针一步，找到待反转部分的第一个节点
    if (m < n) {
        p = p->next;
        ++i;
    }

    // 开始反转待反转部分的节点
    while (i <= n) {
        q = p; // 将 q 指向当前节点 p
        p = p->next; // 移动 p 指针到下一个节点
        ++i; // 计数器加一
        q->next = pre->next; // 将 q 的 next 指针指向待反转部分的前一个节点的下一个节点
        pre->next = q; // 将待反转部分的前一个节点的 next 指针指向 q
    }

    // 将待反转部分的后一个节点 t 的 next 指针指向 p，连接起来
    t->next = p;

    return L; // 返回原链表头指针
}





int main() {
    LinkList L;
    InitList(&L);
    InsertElements(L,5,3,1,5,2,4);
    printf("Original list:\n");
    PrintList(L);
    L = ReverseFromTo(L,1,4);
    printf("Sorted list:\n");
    PrintList(L);
    return 0;
}
